package com.yusong.algorithm.dp;

import java.util.Arrays;

public class MinPath64 {



    public static void main(String[] args) {
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        MinPath64 main= new MinPath64();
        main.minPathSum(grid);
    }



    /**
     * 动态规划
     * 以上一行的数据
     * 状态转移：到达当前网格的最小值 min（到达上方网格的最小值，到达左边网格的最小值）+当前网格值
     */
    public int minPathSum(int[][] grid) {
        int height = grid.length;
        int width = grid[0].length;

        //默认值为0  bad  手动初始化第一行数据
        int[] cacheRoute = new int[width];
        cacheRoute[0] = grid[0][0];
        for(int i = 1; i < width; i++){
            cacheRoute[i] = grid[0][i]+ cacheRoute[i-1];
        }
        //根据上一行的结果依次计算这一行的结果
        for(int j = 1; j < height; j++){
            int[] route = new int[width];
            int[] nums = grid[j];

            for(int i = 0; i < width; i++){
                int num = nums[i];
                int left = Integer.MAX_VALUE;
                if(i > 0){
                    left = route[i-1];
                }
                int top = cacheRoute[i];
                int routeNum = num + Math.min(top, left);
                route[i] = routeNum;
            }
            cacheRoute = route;
        }
        return cacheRoute[width -1];
    }
}



/*
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

[[1,3,1],[1,5,1],[4,2,1]]
7
 */